package 每日一题;

import java.util.Arrays;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-08-26
 **/

public class No881救生艇 {

    /**
     * 第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
     * <p>
     * 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
     * <p>
     * 返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：people = [1,2], limit = 3
     * 输出：1
     * 解释：1 艘船载 (1, 2)
     * 示例 2：
     * <p>
     * 输入：people = [3,2,2,1], limit = 3
     * 输出：3
     * 解释：3 艘船分别载 (1, 2), (2) 和 (3)
     * 示例 3：
     * <p>
     * 输入：people = [3,5,3,4], limit = 5
     * 输出：4
     * 解释：4 艘船分别载 (3), (3), (4), (5)
     * 提示：
     * <p>
     * 1 <= people.length <= 50000
     * 1 <= people[i] <= limit <= 30000
     */

    /**
     * 最少船数量
     */
    public int numRescueBoats(int[] people, int limit) {

        Arrays.sort(people);
        int result = 0;
        int minIndex = 0;
        int single = 0;

        for (int maxIndex = people.length - 1; maxIndex >= 0 && minIndex < maxIndex; maxIndex--) {

            int maxNum = people[maxIndex];
            int minNum = people[minIndex];

            if (maxNum == limit) {
                // No Thing
                single++;
            } else {

                if (minNum + maxNum <= limit) {
                    minIndex++;
                } else {
                    // No Thing
                    single++;
                }

            }

            result++;
        }

        if ((people.length - single) % 2 != 0) {
            result++;
        }

        /**
         * 可以更简单: 一个while就能解决
         */
        return result;
    }

    public int numRescueBoatsGood(int[] people, int limit) {

        Arrays.sort(people);
        int left = 0;
        int right = people.length - 1;
        int result = 0;

        while (left <= right) {

            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
            result++;
        }

        return result;
    }

    public static void main(String[] args) {
        No881救生艇 n = new No881救生艇();
        int[] arr = {1, 2, 1};
        int result = n.numRescueBoatsGood(arr, 3);
        System.out.println(result);
    }

}
